package cn.fxzhang.leetcode.no17;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 1738. 找出第 K 大的异或坐标值
 * 给你一个二维矩阵 matrix 和一个整数 k ，矩阵大小为 m x n 由非负整数组成。
 * 矩阵中坐标 (a, b) 的 值 可由对所有满足 0 <= i <= a < m 且 0 <= j <= b < n 的元素 matrix[i][j]（下标从 0 开始计数）执行异或运算得到。
 * 请你找出 matrix 的所有坐标中第 k 大的值（k 的值从 1 开始计数）。
 *
 * 提示：
 * m == matrix.length
 * n == matrix[i].length
 * 1 <= m, n <= 1000
 * 0 <= matrix[i][j] <= 10^6
 * 1 <= k <= m * n
 *
 * 类型：数值计算
 * 题解：根据公式a^b^b=a,a^b^a=b，可算出f[i][j]
 * 时间复杂度：O(N^2)
 * 空间复杂度：O(N^2)
 *
 * 提交记录(1/1)：
 * 执行用时: 370 ms, 击败了11.51%
 * 内存消耗: 143.3 MB, 击败了80.60%
 *
 * 【中等】通过次数116,961提交次数267,848
 * @author 张晓帆
 * @date 2021/5/19
 */
public class P1738_Find_Kth_Largest_Xor_Coordinate_Value {

    public int kthLargestValue(int[][] matrix, int k) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] f = new int[m][n];
        // 第0行
        List<Integer> list = new ArrayList<>();
        list.add(matrix[0][0]);
        f[0][0] = matrix[0][0];
        for (int i=1; i<n; i++){
            f[0][i] = f[0][i-1]^matrix[0][i];
            list.add(f[0][i]);
        }
        // 第0列
        for (int i=1; i<m; i++){
            f[i][0] = f[i-1][0]^matrix[i][0];
            list.add(f[i][0]);
        }
        for (int i=1; i<m; i++){
            for (int j=1; j<n; j++){
                f[i][j] = f[i-1][j-1]^f[i-1][j]^f[i][j-1]^matrix[i][j];
                list.add(f[i][j]);
            }
        }
        Collections.sort(list);
        return list.get(n*m-k);
    }
}
